/// [1000-digit Fibonacci number](https://projecteuler.net/problem=25)
fn main() {
    for n in &[3, 1000] {
        println!(
            "The first term to contain {} digits is {}",
            n,
            digit_fibonacci_number(*n)
        );
    }
}

fn digit_fibonacci_number(n: usize) -> u64 {
    let big_digit = 36;
    let big_number = 10_u128.pow(big_digit);
    let mut big_num_1 = vec![1];
    let mut big_num_2 = vec![1];
    let mut index = 2;
    while (big_num_2.len() - 1) * big_digit as usize + big_num_2[big_num_2.len() - 1].to_string().len() < n {
        let mut tmp = vec![];
        for i in 0..big_num_1.len() {
            tmp.push(big_num_1[i] + big_num_2[i])
        }
        for i in big_num_1.len()..big_num_2.len() {
            tmp.push(big_num_2[i])
        }
        for i in 0..(tmp.len() - 1) {
            if tmp[i] >= big_number {
                tmp[i + 1] += tmp[i] / big_number;
                tmp[i] %= big_number;
            }
        }
        let i = tmp.len() - 1;
        if tmp[i] >= big_number {
            tmp.push(tmp[i] / big_number);
            tmp[i] %= big_number;
        }
        big_num_1 = big_num_2;
        big_num_2 = tmp;
        index += 1;
    }
    index
}
